\subsection{An $\rb{O(n^\epsilon), O(\log n)}$-approximation algorithm}
\label{sec:approx}
We present an LP-based approximation algorithm, which makes use of the
evolution graph and Lemma~\ref{lem:level.steiner} that connects
$k$-gossip to Steiner tree packing.  If the $k$-gossip problem can be
solved on any $n$-node dynamic network in $L$ rounds, then our
algorithm will solve the $k$-gossip problem on any dynamic network in
$O(n^\epsilon L)$ rounds, assuming each node is allowed to broadcast
$O(\log n)$ tokens, instead of one, in each round.

\junk{
\begin{corollary}
\label{cor:level.steiner}
The $k$-gossip problem can be solved in $l$ rounds if $k$ directed
Steiner trees can be packed in the corresponding evolution graph,
where for each token, the root of its Steiner tree is a source node at
level 0, and the terminals are all the nodes at level $2l$.
\end{corollary}
}

Packing Steiner trees in $m$-edge directed graphs is NP-hard to
approximate even within $\Omega(m^{1/3-\epsilon})$ for any
$\epsilon>0$ \cite{cheriyan+s:steiner}.  Our algorithm solves the
Steiner tree packing problem with a relaxation that allows edge
capacity to blow up by an $O(\log n)$ factor. First, we write down the
LP for the Steiner tree packing problem. Let $\cal T$ be the set of
all possible Steiner trees, and $c_e$ be the capacity of edge $e$. For
each Steiner tree $T\in \cal T$, we associate a variable $x_T$ with
it. If $x_T=1$, then Steiner tree $T$ is in the optimal solution; if
$x_T=0$, it's not. After relaxing the integral constraints on $x_T$'s,
we have the following LP, referred to as $\cal P$ henceforth. Let
$F(\cal P)$ denote the optimal fractional solution for $\cal P$.
\junk{
\begin{eqnarray*}
\max & \sum_{T\in \cal T} x_{T}\\
\mbox{s.t.}& \sum_{T:e\in T} x_{T} \le c_{e} \,\, \forall e\in E \\
 & x_{T} \ge 0 \,\, \forall T\in \cal T
\end{eqnarray*}
}

\[
\max \; \sum_{T\in \cal T} x_{T} \mbox{ subject to } \sum_{T:e\in T} x_{T} \le c_{e}  \,\, \forall e\in E \mbox{ and }  x_{T} \ge 0  \,\, \forall T\in \cal T.
\]

\junk{
\[
\begin{array}{rrr}
\max & \sum_{T\in \cal T} x_{T} & \\
\mbox{s.t.} & \sum_{T:e\in T} x_{T} \le c_{e}  & \,\, \forall e\in E \\
 & x_{T} \ge 0  & \,\, \forall T\in \cal T
\end{array}
\]
}
\junk{
%%%%%%% begin junk %%%%%%%
\begin{eqnarray*}
\min & \sum_{e\in E} c_e y_e \\
\mbox{s.t.} & \sum_{e\in T} y_e \ge 1 \,\, \forall T\in \cal T \\
 & y_e \ge 0 \,\, \forall e\in E
\end{eqnarray*}
%%%%%%% end junk %%%%%%%
}

\junk{
%%%%%%% begin junk %%%%%%%
\begin{lemma}[\cite{jain+ms:steiner}]
\label{thm:approx-steiner}
There is an $\alpha$-approximation algorithm for the fractional
maximum Steiner tree packing problem if and only if there is an
$\alpha$-approximation algorithm for the minimum-weight Steiner tree
problem.
\end{lemma}
\textcolor{red}{Directed or undirected?}
Charikar et al. \cite{charikar+ccdgg:steiner} gives an
$O(n^\epsilon)$-approximation algorithm for the minimum-weight
directed Steiner tree problem. This together with Lemma
\ref{thm:approx-steiner} implies,
%%%%% end junk %%%%%%%
}

\begin{lemma}[\cite{cheriyan+s:steiner}]
\label{thm:approx-pack-steiner}
There is an $O(n^\epsilon)$-approximation algorithm for the fractional
maximum Steiner tree packing problem in directed graphs.
\end{lemma}


\junk{Let $L$ be the number of rounds that an optimal algorithm uses with
every node broadcasting at most one token per round. We present
, which takes $O(n^\epsilon L)$ rounds with
every node broadcasting $O(\log n)$ tokens per round.  Thus it is an 
$\rb{O(n^\epsilon), O(\log n)}$ bicriteria approximation algorithm.
Algorithm \ref{alg:approx} our $\rb{O(n^\epsilon), O(\log n)}$ bicriteria approximation algorithm

}
\begin{algorithm}[ht!]
\caption{$\rb{O(n^\epsilon), O(\log n)}$-approximation
  algorithm}
\label{alg:approx}
\begin{algorithmic}[1]
  \REQUIRE A sequence of communication graphs $G_1,G_2,\dots$
  \ENSURE Schedule to disseminate $k$ tokens.

  \medskip

  \STATE Initialize the set of Steiner trees ${\cal S} = \emptyset$.

  \FOR{$i = 1 \to 2n^\epsilon$}

  \STATE Find $L^*$ such that with the evolution graph $G$ constructed
  from level $0$ to level $2L^*$, the approximate value for $F(\cal
  P)$ is $k/n^{\epsilon}$. In this step, we use the algorithm of
  \cite{cheriyan+s:steiner} to approximate $F(\cal
  P)$. \label{alg.step:lp}

  \STATE Let $x^*_T$ be the value of the variable $x_T$ in the
  solution from step \ref{alg.step:lp}. The number of non-zero
  $x^*_T$'s is polynomial with respect to $k$. Using randomized
  rounding, with probability $x^*_T$ include $T$ in the solution,
  ${\cal S} = {\cal S} \cup \{T\}$. \label{alg.step:round}

  \STATE Remove communication graphs $G_1,G_2,\dots,G_{L^*}$ from the
  sequence, and reduce the remaining graphs' indices by $L^*$.

  \ENDFOR

  \STATE Convert the set $\cal S$ into a token dissemination schedule
  using Lemma~\ref{lem:level.steiner}. \junk{Corollary~\ref{cor:level.steiner}}
\label{alg.step:convert}
\end{algorithmic}
\end{algorithm}

\begin{theorem}
\label{thm:approx}
Algorithm \ref{alg:approx} achieves an $O(n^\epsilon)$ approximation
to the $k$-gossip problem while broadcasting $O(\log n)$ tokens per
round per node, with high probability.
\end{theorem}


%%%%%%%%%%%%%%%%%%%%%
%% \cite{lau:steiner}
